博弈论 2[SG函数]

$SG$函数相关的证明就不说了，直接下定义。

有向图游戏：
把游戏进行中的局面视作一个状态，在当前的状态和进行某些操作后得到的新状态之间连一条有向边，整个图就构成了一个有向图。

$MEX$函数：
规定$MEX(S)$是在集合$S$中最小的，没有出现的非负整数。

$SG$函数：
在有向图游戏中，从状态$x$出去的边有$k$条，得到的新状态分别记作$y_1$，$y_2$......$y_k$，则$SG(x) = MEX(\{SG(y_1),SG(y_2),......,(SG(y_k)\})$。特别的，对于整张图的$SG$函数值为起点的$SG$值。

多个有向图游戏的和：
设共有$m$个有向图游戏，记作$G_1$，$G_2$，...，$G_k$。每次是在$m$个有向图游戏里选一个游戏走一步，记$G$是所有有向图游戏的和，则$SG(G) = SG(G_1) \bigoplus SG(G_2) \bigoplus,......,\bigoplus SG(G_k)$。

游戏判据：
有向图游戏的某个局面必胜，当且仅当当前节点的$SG$值大于$0$。
有向图游戏的某个局面必败，当且仅当当前节点的$SG$值为$0$。
对于多个有向图游戏的和，同样满足。

[POJ 2311]Cutting game
题目大意：有一张$N*M$的格子纸，每次可以沿竖直或水平方向的线剪开。第一个剪出大小为$1$的人胜利。问先手是否必胜。
数据范围：$1 \leq N,M \leq 200$

每次切一下之后，会使得剩下的有向图游戏增多，可以根据上面的多个有向图游戏的和的结论来计算。不过要注意抠掉边界情况，当剩下的局面里有长度为$2$的条时，就一定失败了。具体在做记忆华搜索的时候，可以通过减少枚举范围来做到。本题的$SG$函数公式也比较显然，这里直接给出：

$SG(N,M) = MEX(\{SG(i,M) \oplus SG(N - i,M)\} \cup \{SG(N,i) \oplus SG(N,M - i)\})$

注意，用于记忆化的数组不必每次都重置，对于某个之前搜过的局面，之后的游戏里如果碰到了不会影响游戏状态。如果每次都重置会导致复杂度过高而TLE。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
typedef long long ll;
const int N = 205;
int n,m;
int mem[N][N];
int SG(int n,int m)
{
	if(mem[n][m] != -1)	return	mem[n][m];
	set<int> tb;
	
	for(int i = 2;n - i >= 2;++i)	tb.insert(SG(i,m) ^ SG(n - i,m));
	for(int i = 2;m - i >= 2;++i)	tb.insert(SG(n,i) ^ SG(n,m - i));
	
	int res = 0;
	while(tb.count(res))	++res;
	return mem[n][m] = res;
}
int main()
{
	memset(mem,-1,sizeof mem);
	while(scanf("%d%d",&n,&m) == 2)
	{
		if(SG(n,m))	puts("WIN");
		else puts("LOSE");
	}
    return 0;
}